package _binary_search;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 354. 俄罗斯套娃信封问题
 */
public class No354 {
    private ArrayList<Integer> list;

    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (e1, e2) -> (e1[0] == e2[0] ? (e2[1] - e1[1]) : (e1[0] - e2[0])));
        list = new ArrayList<>();
        list.add(envelopes[0][1]);
        for (int[] envelope : envelopes) {
            int h = envelope[1];

            if (list.get(list.size() - 1) < h) list.add(h);
            else list.set(lowerBound(h), h);
        }
        return list.size();
    }

    private int lowerBound(int x) {
        int left = 0, right = list.size() - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (list.get(mid) < x) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
